Mobile devices are ubiquitous in modern society. Many of these devices come equipped with sensors such as accelerometers and Global Positioning Systems (GPS) that can collect data about the movements of a user. This creates the potential of intelligent applications that recognize the user's activity and take appropriate action. For example, a device might notice that a user is in distress and alert a care giver, it might make decisions regarding whether incoming phone calls should be put through or saved in a message box, or it might monitor a user and provide information to a remote health database.
Applications for recognizing activities from sensor data have been developed in a wide range of fields such as health care, see for example Kang et al. in “A Wearable Context Aware System for Ubiquitous Healthcare” (IEEE Eng. in Medicine and Biology Society, 5192-5195 2006), fitness, see for example Lester et al in “A Practical Approach to Recognizing Physical Activities” (Lecture Notes in Computer Science 3968: pp 1-16), and security, see for example Kale et al in “A Framework for Activity-Specific Human Recognition” (Proc. Int. Conf. Acoustics, Speech, and Signal Processing, Vol. 706). Different types of sensors have been used, e.g., accelerometer data for recognizing physical activities, see for example Lester, and both mobile phone usage data, see for example Farrahi et al in “What Did You do Today? Discovering Daily Routines from Large-Scale Mobile Data” (Proc. ACM Int. Conf. on Multimedia, 849-852) and GPS data in Krumm et al in “Predestination: Inferring Destinations from Partial Trajectories” (Proc. Ubicomp, pp 243-260, 2006) and Liao et al in “Extracting Places and Activities from GPS Traces using Hierarchal Conditional Random Fields” (Intl. J. Robotics Res, Vol. 26(1), pp 119-134), and for analyzing human mobility and other higher-level, temporally extended activities, see for example Eagle et al in “Reality Mining: Sensing Complex Social Systems” (Personal and Ubiquitous Computing, Vol. 10(4), pp 255-268).
Previous work on this problem has shown recognition accuracy can be achieved, above 85%, but through the use of large and complex data sets, see for example Subramanya et al. in “Recognizing Activities and Spatial Context using Wearable Sensors” (Proc. Uncertainty in Artificial Intelligence) and Lester et al in “A Practical Approach to Recognizing Physical Activities” (Lecture Notes in Computer Science 3968, pp 1-16, 2006).
These existing approaches use standard, typically linear, signal processing methods, through which hundreds of signal statistics are computed. Feature extraction tools are then used to determine which of these features are useful for classification, these being what are referred to as “heavy-duty” applications in respect of their processing requirements. While these approaches work well, they require a lot of computing power, and accordingly are not well suited to real-time detection of activities using low-powered devices, including for example cellular telephones, personal digital assistants (PDAs), portable multimedia players, etc where battery lifetime is a major aspect of the devices usability to the user and the manufacturers and service providers marketing. Further these devices do not exploit high performance processors with high clock speeds, large associated RAM memory, and 64-bit processing.
It would therefore be beneficial to exploit an alternative method for representing time series data, such as derived from a GPS or accelerometer within a portable wireless device, which reduces the memory and computational complexity of performing activity recognition. Accordingly, the inventors have adopted nonlinear time series analysis techniques, see for example Kantz et al in “Nonlinear Time Series Analysis” (Cambridge University Press, 2003, ISBN 9780521821506) to extract features from the time series, and then use these extracted features as the inputs to an event classifier. It would also be beneficial for the technique to work with small data sets and accordingly the inventors present a novel approach for classifying time series data using nonparametric nonlinear models built from small data sets. Beneficially, this algorithm can be implemented and perform classification of activities in real time on existing portable wireless devices.
Considering current portable wireless devices then one sensor present within many such devices is an accelerometer, primarily intended for user input to specific activities such as computer games, re-orientating the device display, and providing directions. Considering the accelerometer data obtained then, intuitively, the acceleration recorded by the device is the result of a measurement performed on a non-linear dynamical system, namely the user and consisting of the hips and legs, with their joints, actuations and interaction with the ground when moving without using the device, and additionally their arms and wrists when using the device. Amongst the approaches for reconstructing the essential dynamics of an underlying system using a short sequence of measurements, evenly spaced in time, is the time-delay embedding methods, see for example Sauer et al in “Embedology” (J. Stat. Phys., Vol. 65, pp 579-616, 1991).
Assuming that the dynamics of the underlying system, i.e. the user's body, are noticeably different when performing different activities then the parameters of the different time-delay embedding models can be used to classify new data either to the activity performed or to ascertain the user's identity. The inventors achieve classification performance, comparable to other state-of-art approaches, but by extracting a small number of features from the time series data, instead of the large number of features within these prior art approaches. Beneficially, the memory and computational savings are important, given that for many applications as discussed above this activity recognition would be running in real time as a small component of larger system on a low-powered mobile consumer electronics device.
Further, the inventors demonstrate the use of reconstructed coordinates in a time-delay embedding of a time series as input to a supervised learning algorithm for the subsequent time series classification. Whilst time-delay values have been used as inputs to neural networks, see for example Waibel et al. in “Phoneme Recognition using Time-Delay Neural Networks” (IEEE Trans. Acoustics, Speech and Signal Processing, Vol. 37, No. 3, pp 328-339), the inventors address the incorporation of noise-reduction techniques into the data and also the explicit treatment of the dynamics of the system from which the measurements are derived. As such the inventors have beneficially established a lightweight classification algorithm based on time-delay embeddings that is efficient and may be embedded to run real time on low-powered, low processor speed devices such as consumer portable electronic devices.
Time-delay embedding is an effective technique for creating models of periodic time series data, see for example Takens in “Detecting Strange Attractors in Turbulence” (Dynamical Systems and Turbulence, Vol. 898, pp 365-381). While time-delay embedding has been used extensively in the analysis of nonlinear dynamical systems, see for example Kantz and Sauer, their use in other fields is limited. The inventors in “Activity and Gait Recognition with Time-Delay Embeddings” (Proc. AAAI Conf. Artificial Intelligence, Paper SS-11-04. July 2010) presented an algorithm called Geometric Template Matching (GTM) for building nonparametric classifiers based on time-delay embedding models of time series.
GTM first builds time-delay models from short segments of time series data, chosen at random from the training data set. Subsequently, with an ensemble of K models derived from the data set, K features are extracted from a new segment of time series data by comparing the new segment with each of the K models. These models can be thought of as radial basis functions with a distance function that incorporates both spatial and temporal information. Extending on their own work by focusing on the interpretation of the GTM feature values as a measure of similarity, or, conversely, as a measure of distance the inventors have established algorithms exploiting the distance function based on GTM for unsupervised, supervised and semi-supervised learning of time series data that were generated as measurements from a latent, nonlinear dynamical system.
Such time series data and nonlinear dynamical systems arise in many scenarios, including but not limited to measurements of physiological phenomena, such as electrocardiography (ECG) or electroencephalography (EEG) recordings, to data captured from accelerometers or other wearable sensors. The inventors demonstrate that these clustering algorithms based on GTM achieve better results than other commonly used time series clustering approaches in the prior art, such as dynamic time warping (DTW) as taught by Berndt et al in “Using Dynamic Time Warping to Find Patterns in Time Series” (Proc. AAAI Workshop—Knowledge Discovery in Databases, pp 229-248, 1994).
Within the embodiments of the invention as described within this specification the inventors also address the problem of selecting segments of data from which to build the time-delay models for classification problems. In prior work of the inventors the segments were selected uniformly randomly from the training data. The extension within the embodiments of the invention exploits an alternative approach based on boosting, see for example Freund et al in “A Decision Theoretic Generalization of On-line Learning and an Application to Boosting” (J. Computer and System Sciences, Vol. 55, pp 119-139, 1997), that adaptively builds models throughout the training process with the beneficial aspect of focusing on data segments where the classifier is performing poorly. Beneficially these extensions of time-delay models are compatible with the constraints of running in real time as a small component of larger system on a low-powered mobile consumer electronics device